package 每日一题;

import java.util.Arrays;

public class No74搜索二维矩阵 {

    /**
     * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
     * 每行中的整数从左到右按升序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     *
     * 示例 1：
     * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     * 输出：true
     * 示例 2：
     * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
     * 输出：false
     *  
     * 提示：
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 100
     * -104 <= matrix[i][j], target <= 104
     */

    public boolean searchMatrix(int[][] matrix, int target) {

        if(matrix.length<1){
            return false;
        }

        int allLength=matrix.length;
        int itemLength=matrix[0].length;
        int left=0;
        int right=allLength-1;
        int midLength=(left+right)/2;

        while (left<right){
            if(matrix[midLength][0]>target){
                //前面
                if(midLength==0||matrix[midLength-1][itemLength-1]<target){
                    //边界||断层
                    return false;
                }
                right=midLength-1;
                midLength=(left+right)/2;
            } else if(matrix[midLength][itemLength-1]<target){
                //后面
                if(midLength==allLength-1||matrix[midLength+1][0]>target){
                    //边界||断层
                    return false;
                }
                left=midLength+1;
                midLength=(left+right)/2;
            }else{
                break;//出去
            }
        }
        //出来就是在这段数组里面
        int[] arr=matrix[midLength];
        int i = this.binarySearch(arr, target);
        if(i<0){
            return false;
        }
        return true;
    }

    private int binarySearch(int[] arr,int target){
        int left=0;
        int right=arr.length-1;
        int mid=(left+right)/2;
        while (left<right){
            if(arr[mid]==target){
                return mid;
            }
            if(arr[mid]<target){
                left=mid+1;
                mid=(left+right)/2;
            }else{
                right=mid-1;
                mid=(left+right)/2;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        No74搜索二维矩阵 n=new No74搜索二维矩阵();
        int[][] arr={};
        boolean result = n.searchMatrix(arr, 73);
        System.out.println(result);
    }

}
